/*
 * @lc app=leetcode.cn id=430 lang=typescript
 *
 * [430] 扁平化多级双向链表
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     prev: Node | null
 *     next: Node | null
 *     child: Node | null
 *     constructor(val?: number, prev? : Node, next? : Node, child? : Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.prev = (prev===undefined ? null : prev);
 *         this.next = (next===undefined ? null : next);
 *         this.child = (child===undefined ? null : child);
 *     }
 * }
 */

//  思路：递归
//  处理好递归后的合并，在指向改变之前记录后续要用到的节点

//  复杂度：O(n) O(1)

function flatten(head: Node | null): Node | null {
    let curr = head
    while (curr) {
        if (curr.child) {
            // 处理孩子
            let childBack = flatten(curr.child)
            curr.child = null
            let currNext = curr.next
            if (childBack) {
                // 处理头部
                curr.next = childBack
                childBack.prev = curr
                // 处理尾部
                let end = childBack
                while (end.next) end = end.next
                end.next = currNext
                currNext && (currNext.prev = end)
            }

        }
        curr = curr.next
    }
    return head
};
// @lc code=end

import { Node } from './type'
const head = new Node(1)
const node2 = new Node(2)
const node3 = new Node(3)
const node4 = new Node(4)
const node5 = new Node(5)

head.next = node2
node2.prev = head
node2.child = node3
node3.next = node4
node4.prev = node3
node3.child = node5
console.log(Node.printList(flatten(head)))
